package com.yvon.service.demo.design;

/**
 * <img src="https://kulalasmile.oss-cn-hangzhou.aliyuncs.com/202208161418171.png"/>
 *
 * 当前节点i的父节点： parent = (i - 1) /2
 * 当前节点i的左子节点：c1 = 2i + 1
 * 当前节点i的右子节点：c2 = 2i + 2
 *
 *
 * n代表数组长度
 */
public class Heap {

    public static void main(String[] args) {

    }

    /**
     * 堆排序
     *
     */
    void heapSort(int[] tree, int n) {
        buildHeap(tree, n);
        for (int i = n -1; i >= 0; i --) {
            swap(tree, i, 0);
            heapify(tree, i, 0);
        }
    }

    void buildHeap(int[] tree, int n) {
        // 因为n表示节点的数量即数组的长度，所以最后一个节点坐标为n-1
        int lastNode = n - 1;
        // 当前节点i的父节点： parent = (i - 1) /2
        int parent = (lastNode - 1) /2;
        // 遍历所有的父节点进行heapfy
        for (int i = parent; i >=0; i --) {
            heapify(tree, n, i);
        }
    }


    void heapify(int[] tree, int n, int i) {
        if (i >= n) {
            return;
        }
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if (c1 < n && tree[c1] > tree[max]) {
            max = c1;
        }
        if (c1 < n && tree[c2] > tree[max]) {
            max = c2;
        }
        if (max != i) {
            swap(tree, max, i);
        }
    }

    void swap(int[] tree, int m, int n) {
        int temp = tree[m];
        tree[m] = tree[n];
        tree[n] = temp;
    }
}
